<!DOCTYPE html>
<html>

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <title>标题</title>
</head>

<body>
    <script>

        // 1. 时间复杂度：O(n) / O(nlogn)
        // 平均情况下的时间复杂度O(n) 最坏情况下的时间复杂度O(nlogn)
        // 平均情况：假设n个元素需要排序 分为n个桶 每个桶里面一个元素
        //     - 求最大值和最小值 运算量为n
        //     - 创建空桶 运算量为n
        //     - 把原始数列的元素匹配到空桶里面 运算量为n
        //     - 在桶的内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为n
        //     - 输出排序序列 -> 原始数组 运算量为n
        //     最终为O(n)
        // 最坏的情况：nlogn = nlogn[排序使用] + n = n(logn + 1) 而1可以忽略不计 就是nlogn


        // 2. 空间复杂度：O(n)
        //     - 一个空的数组 -> n

        // 3. 逻辑
        // 总的：把若干个元素放到桶里面去，桶里面的元素各自排序，再把元素取出来就是排序后的结果
        // 1. 求最大值和最小值
        //    如何判断有几个桶？根据最大值和最小值的差 / 每个桶里面的元素个数
        // 2. 如何判断每个元素应该放到哪个桶？ 
        //    创建新的桶 + 内部转化为二维数组
        //    目标元素 - min / 每个桶里面的元素个数
        // 3. 遍历array桶(是个二维)
        //    然后内部归并排序
        //    取出来，放到arr结果数组里面
        function bucketSort(arr, bucketSize) {
            // 判空
            if (!arr.length) {
                return arr
            }
            // 求最大值和最小值
            let max = arr[0]
            let min = arr[0]
            for (let i = 0; i < arr.length; i++) {
                if (arr[i] > max) {
                    max = arr[i]
                } else if (arr[i] < min) {
                    min = arr[i]
                }
            }
            // 设置默认桶大小 
            let default_bucket_size = bucketSize || 5
            // 桶个数
            let bucket_count = Math.ceil((max - min) / default_bucket_size) 
            // 初始化桶
            let array = new Array(bucket_count).fill(0).map(() => [])
            // 每个数放到对应桶
            for (let i = 0; i < arr.length; i++) {
                array[Math.floor((arr[i] - min) / default_bucket_size)].push(arr[i])
            }
            arr = []
            // 桶内各自排序
            for (let i = 0; i < array.length; i++) {
                mergeSort(array[i])
                for (let j = 0; j < array[i].length; j++) {
                    arr.push(array[i][j])
                }
            }
            // 放到arr数组中
            return arr
        }
        console.log(bucketSort([99, 98, 97, 96, 95, 94, 93.4, 92.3, 91.2, 90.1]));

        function mergeSort(arr) {
            mergeArray(arr, 0, arr.length - 1)
            return arr
        }
        function mergeArray(arr, start, end) {
            // 这个是递归的退出条件
            if (start >= end) {
                return
            }
            // 求的是中间值 以此来分组
            let mid = parseInt((start + end) / 2)
            // 注意这个顺序 先左边 后右边
            // 然后再针对当前的 start mid end 进行排序 -> 其实是最小分组先进行排序
            mergeArray(arr, start, mid)
            mergeArray(arr, mid + 1, end)
            _merge(arr, start, mid, end)
        }

        function _merge(arr, start, mid, end) {
            // p1指针在前面半部分，p2指针是后面半部分
            // p指针给到tempArr组合
            // 如果p1小于p2就把p1放到tempArr数组里面去
            let p1 = start,
                p2 = mid + 1,
                p = 0,
                tempArr = [];
            while ((p1 <= mid) && (p2 <= end)) {
                // 注意 为了是原地排序 这里要是<= 如果是等于的情况 就把左边的先放进去，这样相对的位置就不会改变了
                if (arr[p1] <= arr[p2]) {
                    tempArr[p++] = arr[p1++]
                } else {
                    tempArr[p++] = arr[p2++]
                }
            }
            // 有情况就是p1的值并没有完全放到tempArr或者是p2的  
            while (p1 <= mid) {
                tempArr[p++] = arr[p1++]
            }
            while (p2 <= end) {
                tempArr[p++] = arr[p2++]
            }
            // 注意思考，为什么这里是遍历tempArr数组呢，因为这个是排序好的结果。为什么是arr[i + start] 因为start开始的地方可能是不同的
            for (let i = 0; i < tempArr.length; i++) {
                arr[i + start] = tempArr[i]
            }
        }
    </script>
</body>

</html>